1. Field of the Invention
The present invention concerns the technical field of cryptography, and the present invention particularly concerns the technical field of the constant monitoring of cryptographic circuits for occurring errors in running operation.
2. Description of the Related Art
Due to the significant expansion of modern-day data transmission, for example via electronic mail (e-mail) via the internet, there is also increasing interest in being able to transfer personal or secret data via mostly insecure message transfer channels (such as an internet connection) in a protected manner. For this, various approaches have been proposed, such as the method outlined in the “Data Encryption Standard” (DES). It is to be noted, however, that with the increase in available computing capacity such a cryptographic method may be “cracked” also by non-authorized persons, employing high numerical expense. Hereby, a need for further increase in the security of cryptographic methods results. Such an enhanced cryptographic method has been proposed, for example, in the proposals for an enhanced cryptographic standard like the “Advanced Encryption Standard” (AES) by J. Daemen and V. Rijmen in the document “AES proposal: Rijndael”.
In this AES proposal, in successive rounds, an unencrypted text is transformed into an encrypted text, which is again decrypted in successive rounds after transfer to a receiver. Here, in one round, the operations of a non-linear substitution, Shift-Row, MixColumn, and AddKey are used, as illustrated in detail in the article “AES proposal: Rijndael” by J. Daemen and V. Rijmen.
The use of the AES algorithm proposed, however, does not always guarantee reliable communication or encryption. Previous works have shown that even in individual occurring errors during the encryption with the AES algorithm (or a decryption algorithm corresponding to a decryption with the AES algorithm) a high number of errors in the encrypted or decrypted data are very likely to result.
Prior to the transfer of such erroneous data or the output of such erroneous data, these errors have to be recognized in order to avoid data transfer of erroneous data on the one hand and at the same time also prevent output erroneous data from being used to be able to derive sensitive information from the encryption or decryption algorithm (such as the secret encryption or decryption key) on the other hand.
The error recognition for the above-described AES algorithm may, for example, take place by a parity code, as it is described in G. Bertoni, L. Breveglieri, I. Koren and V. Piuri, “Error Analysis and Detection Procedures for a Hardware Implementation of the Advanced Encryption Standard”, IEEE Transactions on Computers, vol. 52, No. 4, pages 492-505, April 2003. A further possibility for the error recognition for the AES algorithm is described in Wu K., Karri R., Kuznetsov, G. and Goessel M., “Low Cost Concurrent Error Detection for the Advanced Encryption Standard”, Preprint 008/2003, October 2003, ISSN 0946-7580, University of Potsdam, Institute for Computer Science, as it is also explained in DE 10261810.
Thus, in Wu K., Karri R., Kuznetsov, G. and Goessel M., “Low Cost Concurrent Error Detection for the Advanced Encryption Standard”, Preprint 008/2003, October 2003, ISSN 0946-7580, University of Potsdam, Institute for Computer Science, the parity of the input values of a round of the AES algorithm is transformed into the parity of the output values of the same round and compared with the actual, possibly inverted parity of the output values for each round.
If the parity transformed into the output parity and the actual output parity do not match, an error is indicated.
Here, both technically induced errors and intentionally injected errors are recognized if they corrupt an odd number of bits.
By intentionally injected errors, such as by selective irradiating the circuit, by changes in the operating voltage, by heating, and other measures, attackers may seek to change the chip so that they can determine the key used in the encryption/decryption of a round with less complexity than would be possible in a non-faulty chip.
In order to indicate an error, as mentioned above, in the approach previously proposed by Wu K., Karri R., Kuznetsov, G. and Goessel M., the parity transformed into the inverted output parity and the actual output parity are calculated, and if these do not match, an error is indicated. Such a possibility for the recognition of an occurred error is illustrated in FIG. 6 in greater detail, which shows a circuit for the implementation of successive rounds of the AES algorithm with error recognition using a parity code, as corresponds to the approach shown in DE 10261810 and thus is to be regarded as prior art.
FIG. 7A shows a cryptographic circuit KS 51 for encrypting or for decrypting data with error recognition by a parity code, according to the prior art. At its n inputs, the n binary input signals x1, . . . , xn are present. Here, n has been assumed to be equal to 128. From these input signals, an input parityP(x)=x1⊕ . . . ⊕xn is formed in the XOR tree 52. The input signals x1, . . . , xn are processed into the output signals v1 . . . vn in l, l≧1, successive processing steps in the cryptographic circuit KS 51. Corresponding to the l processing steps executed in the cryptographic circuit KS 51, the parity P(x) of the input signals is modified by modifying parity signals MP1, . . . , MP1, which are linked with the parity P(x) of the input signals by the XOR gates 54 and 55 to the modified parity PM.
From the outputs v1, . . . , vn of the cryptographic circuit KS 51, the parity P(v) of the outputs, P(v)=v1 ⊕ . . . ⊕vn, is formed in the XOR tree 53. The modified parity PM and the parity of the outputs P(v) are compared at the outputs r1 and r2. If the modified parity PM is equal to the parity of the outputs P(v), no recognizable error is present. A difference of both values indicates an error.
A concrete design of a cryptographic circuit with error recognition for the AES algorithm according to the prior art is illustrated in FIG. 7B.
In FIG. 7B, a circuit, in which n is chosen to be equal to 128, is shown. The cryptographic circuit KS consists of the circuit parts performing the non-linear substitution of the data in the S boxes 1, the operation Shift Rows 3, the operation MixColumns 4, and the operation AddKey 5. In the XOR tree 7, the parity of the respectively present inputs is formed.
Corresponding to the processing step “non-linear substitution”, the parity of the inputs is modified by the parityMP1=p(x1)⊕p(y1)⊕ . . . ⊕p(x16)⊕p(y16)formed in the XOR tree 8 (referring back to the nomenclature of FIG. 7A). Since the operations “Shift Rows” and “MixColumns” for the AES algorithm do not cause modification of the parity, no modifying parity signal is required for these operations.
The modification of the parity by the operation “AddKey” takes place by the modulo 2 addition of the parity P(K) of the key K=k1, . . . , k128 with P(K)=k1⊕ . . . ⊕k128 in the XOR gate 10. It can be recognized that in the concrete case from FIG. 7B as opposed to the case in FIG. 7A 1=2 and MP2=P(K) applies.
The processing of the data takes place in the AES algorithm in successive rounds, in which the output signals of the i-th round are the input signals of the (i+1)-th round.
Thereby, it is possible that in the concrete case of the AES the function of the parity tree 53 in FIG. 7A may be taken over from the parity tree 7 in FIG. 7B. For this, the output signals of the cryptographic circuit in FIG. 7B obtained in a round i, which are here the outputs of the operation “AddKey” 5, are latched in a register 6 and again input in the cryptographic circuit as input signals in the next (i+1)-th round. It can be realized that then the parity of the outputs of the i-th round, which is equal to the parity of the input signals of the (i+1)-th round, is calculated in the parity tree 7.
If the modified parity PM is delayed in the register 11 of FIG. 7B, at the outputs r2 and r1 the modified parity of the inputs of the i-th round and the parity of the outputs of the i-th round are compared.
An additional parity tree, such as the parity tree 53 in FIG. 7A, could of course also be used at the outputs of the operation “AddKey”. But since, as has already been set forth, the data processing in the AES takes place in successive rounds, the parity calculation of the parity of the output signals may functionally also be made in the parity tree for the calculation of the parity of the inputs.
In the circuit of FIG. 7B, n is also chosen to be equal to 128. The cryptographic circuit KS consists of the circuit parts performing the non-linear substitution of the data in the S boxes, the operation Shift Rows 3, the operation MixColumns 4, and the operation AddKey 5. In the XOR tree 7, the parity of the respectively present inputs is formed.
The input x assumed as 128 bits wide in FIG. 7B is divided into 16 bit groups x1=x1, . . . , x8, . . . , x16=x121, . . . , x128 each 8 bits wide, which are each processed by one of the 16 non-linear functions S into the bit group y1=y1, . . . , y8, . . . , y16=y121, . . . , y128. The function S is also referred to as S box 1 and may, for example, be realized by a ROM.
As shown in Wu K., Karri R., Kuznetsov, G. and Goessel, M., the i-th S box has an additional 9th output in i=1, . . . 16, which realizes the function p(xi)⊕p(yi), wherein p(x1) and p(yi) designate the parity of the input signals xi of the i-th S box and the parity of the output signals yi of the i-th S box, respectively, so that, for example,p(x1)⊕p(y1)=x1⊕x2⊕ . . . ⊕x8⊕y1⊕y2⊕ . . . y8 applies, with the operator ⊕ designating XORing.
The inputs of the circuit x1, . . . , x16=x1, . . . , x8, . . . , x121, . . . , x128 are linked to the parity P(x) in a parity tree 7, directly present at the output 12 for error recognition.
In the XOR tree 8, the parities p(xi)⊕p(yi), . . . , p(x16)⊕p(y16) are XORed. The output of the XOR tree 8 is linked with the parity P(x) to p(y) in the XOR gate 9.
The outputs y(t)=yi, . . . , y16 of the S boxes 1 are processed into the binary values z(t) (which may change in the course of time and thus depend on the time parameter t) by the row shift operation Shift-Rows 3, with the parity not changing. Furthermore, the values z(t) are transformed into the values u(t) by the column mix operation MixColumn 4, wherein the values u(t) are also time-variable, and wherein their parity also does not change. In the subsequent operation of adding a key AddKey 5, the values of a binary key K are modulo 2 added to the values u(t) component-wise so that the values of v(t) result, which are also variable in the course of time. Subsequently, the values v(t) are latched in a register 6 and again fed to the AES algorithm illustrated in FIG. 7B as input values x in an ensuing next round, whereby the AES algorithm obtains a recursive structure.
The output of the XOR gate 9 carrying the signal P(y) is linked with the parity P(K) of the key K to PM(v(t)) in the XOR gate 10. The input parity P(x(t)) has been modified into the parity PM(v(t)) here, so that in the error-free case the modified parity PM(v(t)) is equal to the parity P(v(t)) of the binary output values v(t)=v1(t), . . . , v128(t).
The output values v(t) of the operation AddKey 5 are stored in the register 6 and connected to the inputs of the circuit in the next clock via a multiplexer, which is not drawn, so that now in the next clock t+1 in the XOR tree 7 the parity signal P(v(t)) is output directly to the output r1. The binary signal PM(v(t)) output by the XOR gate 10 is stored in the register 11 for one clock and output directly to the output r2 13, so that at the outputs r1 12 and r2 13 the signals P(v(t)) and PM(v (t)) are compared with each other in the clock t+1. A difference of both signals indicates an error.
By the error signal indicating an error in the parity of the non-monitored data, however, a potential attacker may for example obtain additional information on the number of ones and zeros present in the data words, which is disadvantageous.
In U.S. Pat. No. 5,365,591, it is described how an error recognition in a cryptographic system may be implemented using pseudo-random signals for a multiprocessor system preferably implementing the DES algorithm, so that the output values of the comparators used there alternate. It is disadvantageous that such an implementation is very intensive and that the method described cannot or not easily be employed for complex algorithms, such as the AES algorithm.